Search Results

Documents authored by Levi Alev, Vedat

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.18
Approximating Unique Games Using Low Diameter Graph Decomposition

Authors: Vedat Levi Alev and Lap Chi Lau

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We design approximation algorithms for Unique Gmeas when the constraint graph admits good low diameter graph decomposition. For the M2Lin(k) problem in K(r)-minor free graphs, when there is an assignment satisfying 1-eps fraction of constraints, we present an algorithm that produces an assignment satisfying 1-O(r*eps) fraction of constraints, with the approximation ratio independent of the alphabet size. A corollary is an improved approximation algorithm for the Min-UnCut problem for K(r)-minor free graphs. For general Unique Games in K(r)-minor free graphs, we provide another algorithm that produces an assignment satisfying 1-O(r *sqrt(eps)) fraction of constraints. Our approach is to round a linear programming relaxation to find a minimum subset of edges that intersects all the inconsistent cycles. We show that it is possible to apply the low diameter graph decomposition technique on the constraint graph directly, rather than to work on the label extended graph as in previous algorithms for Unique Games. The same approach applies when the constraint graph is of genus g, and we get similar results with r replaced by log g in the M2Lin(k) problem and by sqrt(log g) in the general problem. The former result generalizes the result of Gupta-Talwar for Unique Games in the M2Lin(k) case, and the latter result generalizes the result of Trevisan for general Unique Games.
Cite as

Vedat Levi Alev and Lap Chi Lau. Approximating Unique Games Using Low Diameter Graph Decomposition. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{levialev_et_al:LIPIcs.APPROX-RANDOM.2017.18,
  author =	{Levi Alev, Vedat and Lau, Lap Chi},
  title =	{{Approximating Unique Games Using Low Diameter Graph Decomposition}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.18},
  URN =		{urn:nbn:de:0030-drops-75676},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.18},
  annote =	{Keywords: Unique Games, Low Diameter Graph Decomposition, Bounded Genus Graphs, Fixed Minor Free Graphs, Approximation Algorithms, Linear Programming}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact